package ai.zixing.mashibing.advance_class.first.class06;

public class Code01_MorrisTraversal {

    public static class Node{
        int value;
        Node left;

        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    // 空间复杂度 O(1) 利用的是树中的空闲指针
    // 时间复杂度 O(N)
    public static void morris(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            // cur 有子树
            if (mostRight != null) {
                // 找到 cur 左树上的真实的【原始树】最右节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                // while 中出来， mostRight 一定是 cur 左树上的最右节点
                // 第一次到达
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else { // mostRight.right = cur
                    mostRight.right = null;
                }
            }
            // cur 没有子树，往右移动
            cur = cur.right;
        }
    }

    // 中序遍历
    private static void morrisIn(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
        System.out.println();
    }
}
